{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Query Kth Smallest Trimmed Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #divide-and-conquer #quickselect #radix-sort #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #分治 #快速选择 #基数排序 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestTrimmedNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #裁剪数字后查询第 K 小的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串数组&nbsp;<code>nums</code>&nbsp;，其中每个字符串 <strong>长度相等</strong>&nbsp;且只包含数字。</p>\n",
    "\n",
    "<p>再给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [k<sub>i</sub>, trim<sub>i</sub>]</code>&nbsp;。对于每个&nbsp;<code>queries[i]</code>&nbsp;，你需要：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将&nbsp;<code>nums</code>&nbsp;中每个数字 <strong>裁剪</strong>&nbsp;到剩下 <strong>最右边</strong>&nbsp;<code>trim<sub>i</sub></code>&nbsp;个数位。</li>\n",
    "\t<li>在裁剪过后的数字中，找到 <code>nums</code>&nbsp;中第&nbsp;<code>k<sub>i</sub></code>&nbsp;小数字对应的 <strong>下标</strong>&nbsp;。如果两个裁剪后数字一样大，那么下标 <strong>更小</strong>&nbsp;的数字视为更小的数字。</li>\n",
    "\t<li>将 <code>nums</code>&nbsp;中每个数字恢复到原本字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个长度与 <code><span style=\"\">queries</span></code>&nbsp;相等的数组<em>&nbsp;</em><code>answer</code>，其中<em>&nbsp;</em><code>answer[i]</code>是第<em>&nbsp;</em><code>i</code><em>&nbsp;</em>次查询的结果。</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>裁剪到剩下最右边 <code>x</code>&nbsp;个数位的意思是不断删除最左边的数位，直到剩下 <code>x</code>&nbsp;个数位。</li>\n",
    "\t<li><code>nums</code>&nbsp;中的字符串可能会有前导 0 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [\"102\",\"473\",\"251\",\"814\"], queries = [[1,1],[2,3],[4,2],[1,2]]\n",
    "<b>输出：</b>[2,2,1,0]\n",
    "<strong>解释：</strong>\n",
    "1. 裁剪到只剩 1 个数位后，nums = [\"2\",\"3\",\"1\",\"4\"] 。最小的数字是 1 ，下标为 2 。\n",
    "2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。\n",
    "3. 裁剪到剩 2 个数位后，nums = [\"02\",\"73\",\"51\",\"14\"] 。第 4 小的数字是 73 ，下标为 1 。\n",
    "4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。\n",
    "   注意，裁剪后数字 \"02\" 值为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [\"24\",\"37\",\"96\",\"04\"], queries = [[2,1],[2,2]]\n",
    "<b>输出：</b>[3,0]\n",
    "<strong>解释：</strong>\n",
    "1. 裁剪到剩 1 个数位，nums = [\"4\",\"7\",\"6\",\"4\"] 。第 2 小的数字是 4 ，下标为 3 。\n",
    "   有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。\n",
    "2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i].length &lt;= 100</code></li>\n",
    "\t<li><code>nums[i]</code> 只包含数字。</li>\n",
    "\t<li>所有&nbsp;<code>nums[i].length</code>&nbsp;的长度 <b>相同</b>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 100</code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= k<sub>i</sub> &lt;= nums.length</code></li>\n",
    "\t<li><code>1 &lt;= trim<sub>i</sub> &lt;= nums[0].length</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能使用 <strong>基数排序算法</strong> 解决此问题吗？这种解法的复杂度又是多少？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [query-kth-smallest-trimmed-number](https://leetcode.cn/problems/query-kth-smallest-trimmed-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [query-kth-smallest-trimmed-number](https://leetcode.cn/problems/query-kth-smallest-trimmed-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"102\",\"473\",\"251\",\"814\"]\\n[[1,1],[2,3],[4,2],[1,2]]', '[\"24\",\"37\",\"96\",\"04\"]\\n[[2,1],[2,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n \n",
    "        for i, (k, t) in enumerate(queries):\n",
    "            h = []\n",
    "            for j, x in enumerate(nums):\n",
    "                heappush(h, (x[-t:], j))\n",
    "            for _ in range(k - 1):\n",
    "                heappop(h)\n",
    "            ans[i] = h[0][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        for i in queries:\n",
    "            tmp = []\n",
    "            for j in nums:\n",
    "                tmp.append(j[-i[-1]:])\n",
    "            tmp = [(int(i), index) for index, i in enumerate(tmp)]\n",
    "            tmp.sort()\n",
    "            result.append(tmp[i[0]-1][-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # def process(nums: List[str], k:int, trim: int) -> int:\n",
    "        #     trimed = [int(x[0-trim:]) for x in nums]\n",
    "        #     print(trimed)\n",
    "        #     snums = sorted(trimed)\n",
    "        #     print(snums)\n",
    "        #     min = snums[k-1]\n",
    "        #     if k == 1:\n",
    "        #         return trimed.index(min)\n",
    "        #     else:\n",
    "        #         n = snums.count(min)\n",
    "        #         print(f\"k={k},n={n},min={min},trimed={trimed}\")\n",
    "        #         if n == 1:\n",
    "        #             return trimed.index(min)\n",
    "        #         if snums.index(min) >= k-1:\n",
    "        #             return  trimed.index(min)\n",
    "        #         i = 1\n",
    "        #         idx = 0\n",
    "        #         while i <= n and i <= k:\n",
    "        #             # \n",
    "        #             start = 0\n",
    "        #             if i > 1:\n",
    "        #                 start = idx + 1\n",
    "        #             print(f\"i={i},n={n},min={min},start={start},trimed={trimed}\")\n",
    "        #             idx = trimed.index(min, start)\n",
    "        #             i += 1\n",
    "        #         return idx\n",
    "            \n",
    "\n",
    "\n",
    "        # ans = []\n",
    "        # for query in queries:\n",
    "        #     k = query[0]\n",
    "        #     trim = query[1]\n",
    "        #     idx = process(nums, k, trim)\n",
    "        #     ans.append(idx)\n",
    "        # return ans\n",
    "\n",
    "        return [sorted((s[-trim:], i) for i, s in enumerate(nums))[k - 1][1] for k, trim in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for k,t in queries:\n",
    "            tmp = []\n",
    "            for i,num in enumerate(nums):\n",
    "                tmp.append((int(num[-t:]), i))\n",
    "            tmp.sort()\n",
    "            ans.append(tmp[k-1][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        l, times, ans, slen = nums.__len__(), queries.__len__(), [], len(nums[0])\n",
    "        for i in range(times):\n",
    "            k, length = queries[i][0], queries[i][1]\n",
    "            arr = []\n",
    "            start = slen - length\n",
    "            for j in range(l):\n",
    "                # print(\"nums={}, j={}, start={}, num={}\".format(nums, j, start, nums[j][start:]))\n",
    "                arr.append([j, int(nums[j][start:])])\n",
    "            sa = sorted(arr, key=lambda row: row[1])\n",
    "            # print(sa, \"start=\", start)\n",
    "            ans.append(sa[k-1][0])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        return [sorted((s[-trim:], i) for i, s in enumerate(nums))[k - 1][1] for k, trim in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            a = []\n",
    "            for i, x in enumerate(nums):\n",
    "                heappush(a, (int(x[-trim:]), i))\n",
    "            for i in range(k-1):\n",
    "                heappop(a)\n",
    "            ans.append(heappop(a)[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 直接排序，对每个询问，按照题目要求排序，取第 k 小的元素的下标。\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        return [sorted((s[-trim:], i) for i, s in enumerate(nums))[k - 1][1] for k, trim in queries]\n",
    "\n",
    "    # 离线 + 增量排序\n",
    "    def smallestTrimmedNumbers2(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        idx = list(range(len(nums)))\n",
    "        ans, j = [0] * len(queries), 1\n",
    "        for qi, (k, trim) in sorted(enumerate(queries), key=lambda q: q[1][1]):  # 按 trim 排序\n",
    "            while j <= trim:\n",
    "                idx.sort(key=lambda i: nums[i][-j])  # 只比较倒数第 j 个字符的大小\n",
    "                j += 1\n",
    "            ans[qi] = idx[k - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        ans = [0 for _ in range(m)]\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            nn = [(i, x[-y::]) for i, x in enumerate(nums)]\n",
    "            mn = heapq.nsmallest(x, nn, key=lambda x: x[1])[-1]\n",
    "            #print(nn, mn)\n",
    "            ans[i] = mn[0]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        return [sorted([[num, i] for i, num in enumerate(nums)], key = lambda x: x[0][-trim:])[k - 1][1] for k, trim in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = []\n",
    "        for k, trim in queries:\n",
    "            a = [(int(nums[i][-trim:]), i) for i in range(n)]\n",
    "            a.sort()\n",
    "            ret.append(a[k-1][1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            tmp = []\n",
    "            for i, s in enumerate(nums):\n",
    "                tmp.append((s[-trim:], i))\n",
    "            tmp.sort(key=lambda x: x[0])\n",
    "            ans.append(tmp[k-1][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # nums = [\"102\",\"473\",\"251\",\"814\"], queries = [[1,1],[2,3],[4,2],[1,2]]\n",
    "        s_length, res = len(nums[0]), []\n",
    "        for k, t in queries:\n",
    "            ans = []\n",
    "            for i, s in enumerate(nums):\n",
    "                ans.append((int(s[s_length - t:]), i))\n",
    "            ans.sort()\n",
    "            res.append(ans[k - 1][1])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        nn=len(nums[0])\n",
    "        ans=[]\n",
    "        for i,j in queries:\n",
    "            temp=[]\n",
    "            for s in nums:\n",
    "                temp.append(s[nn-j:])\n",
    "            temps=list(range(len(temp)))\n",
    "            temps.sort(key=lambda x:(temp[x],x))\n",
    "            ans.append(temps[i-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for k, t in queries:\n",
    "            x = list(zip([num[-t:] for num in nums], range(n)))\n",
    "            x.sort()\n",
    "            ans.append(x[k - 1][1])\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            tmp=[(num[-trim:], i) for i, num in enumerate(nums)]\n",
    "            tmp.sort()\n",
    "            ans.append(tmp[k-1][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            a = []\n",
    "            for i, x in enumerate(nums):\n",
    "                heappush(a, (x[-trim:], i))\n",
    "            for i in range(k-1):\n",
    "                heappop(a)\n",
    "            ans.append(heappop(a)[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        return [sorted((s[-trim:], i) for i, s in enumerate(nums))[k - 1][1] for k, trim in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1]*len(queries)\n",
    "        buckets = [[] for _ in range(10)]\n",
    "        buckets1 = [[] for _ in range(10)]\n",
    "        lastTrim = 1\n",
    "        for i, n in enumerate(nums):\n",
    "            buckets[0].append((n, i))\n",
    "        for trim, k, i in sorted((trim, k, i) for i, (k, trim) in enumerate(queries)):\n",
    "            for t in range(lastTrim, trim+1):\n",
    "                for n in range(10):\n",
    "                    buckets1[n].clear()\n",
    "                for tt in chain.from_iterable(buckets):\n",
    "                    buckets1[int(tt[0][-t])].append(tt)\n",
    "                buckets1, buckets = buckets, buckets1\n",
    "            lastTrim = trim\n",
    "            for arr in buckets:\n",
    "                if k > len(arr):\n",
    "                    k -= len(arr)\n",
    "                else:\n",
    "                    ans[i] = arr[k-1][1]\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        ans = [0 for _ in range(m)]\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            nn = [(i, x[-y::]) for i, x in enumerate(nums)]   # (index, value)\n",
    "            ans[i] = heapq.nsmallest(x, nn, key=lambda x: x[1])[-1][0]   # kth value\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # 策略：采取基数排序\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        # vecs记录第i轮排序的第j小的元素在nums中对应的下标\n",
    "        vecs = [[] for _ in range(m+1)]\n",
    "        for i in range(n):\n",
    "            vecs[0].append(i)\n",
    "        for i in range(1,m+1):\n",
    "            # 建立10个临时链表，B[i]记录本轮基数为i的元素\n",
    "            B = [[] for _ in range(10)]\n",
    "            for j in vecs[i-1]:\n",
    "                B[ord(nums[j][m-i])-ord('0')].append(j)\n",
    "            for j in range(10):\n",
    "                for k in B[j]:\n",
    "                    vecs[i].append(k)\n",
    "        \n",
    "        ans = []\n",
    "        for item in queries:\n",
    "            ans.append(vecs[item[1]][item[0]-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        mapping = {}\n",
    "        tmp = list(range(n))\n",
    "        for j in range(m-1,-1,-1):\n",
    "            cnts = [[] for _ in range(10)]\n",
    "            for i in tmp:\n",
    "                cnts[int(nums[i][j])].append(i)\n",
    "            mapping[m-j] = []\n",
    "            for cnt in cnts:\n",
    "                mapping[m-j] += cnt \n",
    "            tmp = mapping[m-j]\n",
    "        result = []\n",
    "        for k, trim in queries:\n",
    "            result.append(mapping[trim][k-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        nums = [(num, i) for i, num in enumerate(nums)]\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            k, t = q\n",
    "            arr = [(num[-t:], i) for num, i in nums]\n",
    "            arr.sort()\n",
    "            ans.append(arr[k-1][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        for k, t in queries:\n",
    "            tmp = []\n",
    "            for i, strnum in enumerate(nums):\n",
    "                num = int(strnum[-t:])\n",
    "                tmp.append((num, i))\n",
    "            tmp.sort(key=lambda x:(x[0], x[1]))\n",
    "            ans.append(tmp[k-1][1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n , N = len(nums[0]), len(nums)\n",
    "        ret = []\n",
    "        for k, t in queries:\n",
    "            v = [(nums[i][n - t:], i) for i in range(N)]\n",
    "            v.sort()\n",
    "            ret.append(v[k-1][1])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        nn=len(nums[0])\n",
    "        ans=[]\n",
    "        for i,j in queries:\n",
    "            temp=[]\n",
    "            for s in nums:\n",
    "                temp.append(s[nn-j:])\n",
    "            temps=sorted(range(len(temp)),key=lambda x:(temp[x],x))\n",
    "            ans.append(temps[i-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # n, m = len(nums), len(queries)\n",
    "        # ans = []\n",
    "        # for k, trim in queries:\n",
    "        #     a = []\n",
    "        #     for i, x in enumerate(nums):\n",
    "        #         heappush(a, (x[-trim:], i))\n",
    "        #     for i in range(k-1):\n",
    "        #         heappop(a)\n",
    "        #     ans.append(heappop(a)[1])\n",
    "        # return ans\n",
    "\n",
    "        # 基数排序\n",
    "        idx = list(range(len(nums)))\n",
    "        ans, j = [0]*len(queries), 1\n",
    "        for qi, (k, trim) in sorted(enumerate(queries), key=lambda q: q[1][1]):\n",
    "            while j <= trim:\n",
    "                idx.sort(key=lambda i: nums[i][-j])\n",
    "                j += 1\n",
    "            ans[qi] = idx[k-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # for i, arr in enumerate(queries):\n",
    "        #     arr.append(i)\n",
    "\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            arr = [(int(x[-trim:]), i) for i, x in enumerate(nums)]\n",
    "            arr.sort()\n",
    "            ans.append(arr[k - 1][1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        \n",
    "        # 对于每个查询\n",
    "        for ki, trimi in queries:\n",
    "            # 裁剪nums中的每个数字字符串\n",
    "            trimmed_nums = [(num[-trimi:], index) for index, num in enumerate(nums)]\n",
    "            \n",
    "            # 排序裁剪后的数字字符串并保留它们的原始索引\n",
    "            trimmed_nums.sort(key=lambda x: (x[0], x[1]))\n",
    "            \n",
    "            # 添加第ki小的数字的索引到答案列表中\n",
    "            answer.append(trimmed_nums[ki-1][1])\n",
    "        \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # 策略：采取基数排序\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        # vecs记录第i轮排序的第j小的元素在nums中对应的下标\n",
    "        vecs = [[] for _ in range(m+1)]\n",
    "        for i in range(n):\n",
    "            vecs[0].append(i)\n",
    "        for i in range(1,m+1):\n",
    "            B = [[] for _ in range(10)]\n",
    "            for j in vecs[i-1]:\n",
    "                B[ord(nums[j][m-i])-ord('0')].append(j)\n",
    "            for j in range(10):\n",
    "                for k in B[j]:\n",
    "                    vecs[i].append(k)\n",
    "        \n",
    "        ans = []\n",
    "        for item in queries:\n",
    "            ans.append(vecs[item[1]][item[0]-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        # 1 <= nums.length <= 100 ;; 随便做\n",
    "        @cache\n",
    "        def f(t):\n",
    "            arr = sorted([(int(x[-t:]), i) for i, x in enumerate(nums)])\n",
    "            return [i for v, i in arr]\n",
    "        \n",
    "        ans = []\n",
    "        for k, t in queries:\n",
    "            ans.append(f(t)[k-1])\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        qs = sorted(zip(queries, range(len(queries))), key=lambda q: q[0][1]) # 按 trim 排序，同时保留下标\n",
    "        a = sorted(zip(nums, range(len(nums))), key=lambda n: n[0][-1])       # 按照最后一个字符排序\n",
    "        ans, j = [0] * len(queries), 2        # 初始最后一个排好了，下次要排序倒数第2个字符\n",
    "        for (k, trim), i in qs:               # 遍历queries\n",
    "            while j <= trim:                  # 如果还没有排序到 trim个字符\n",
    "                a.sort(key=lambda n: n[0][-j])# 按照倒数第j个字符排序（增量排序）\n",
    "                j += 1                        # 下一个要排序的字符\n",
    "            ans[i] = a[k-1][1]                # 第k小的索引\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        mapping = {}\n",
    "        tmp = list(range(n))\n",
    "        for j in range(m-1,-1,-1):\n",
    "            cnts = [[] for _ in range(10)]\n",
    "            for i in tmp:\n",
    "                cnts[int(nums[i][j])].append(i)\n",
    "            mapping[m-j] = []\n",
    "            for cnt in cnts:\n",
    "                mapping[m-j] += cnt \n",
    "            tmp = mapping[m-j]\n",
    "        result = []\n",
    "        for k, trim in queries:\n",
    "            result.append(mapping[trim][k-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        mapping = {}\n",
    "        tmp = list(range(n))\n",
    "        for j in range(m-1,-1,-1):\n",
    "            cnts = [[] for _ in range(10)]\n",
    "            for i in tmp:\n",
    "                cnts[int(nums[i][j])].append(i)\n",
    "            mapping[m-j] = []\n",
    "            for cnt in cnts:\n",
    "                mapping[m-j] += cnt \n",
    "            tmp = mapping[m-j]\n",
    "        result = []\n",
    "        for k, trim in queries:\n",
    "            result.append(mapping[trim][k-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        idx = list(range(len(nums)))\n",
    "        ans, j = [0] * len(queries), 1\n",
    "        for qi, (k, trim) in sorted(enumerate(queries), key=lambda q: q[1][1]):  # 按 trim 排序\n",
    "            while j <= trim:\n",
    "                idx.sort(key=lambda i: nums[i][-j])  # 只比较倒数第 j 个字符的大小\n",
    "                j += 1\n",
    "            ans[qi] = idx[k - 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        row = len(nums)\n",
    "        col = len(nums[0])\n",
    "        rank = [[] for _ in range(col+5)]\n",
    "        rank[0] = list(range(row))\n",
    "        for i in range(1,col+1):\n",
    "            buckets =  [[] for _ in range(10)]\n",
    "            for index in rank[i-1]:\n",
    "                buckets[int(nums[index][-i])].append(index)\n",
    "            for bucket in buckets:\n",
    "                rank[i].extend(bucket)\n",
    "        \n",
    "        res = []\n",
    "        for k, trim in queries:\n",
    "            res.append(rank[trim][k-1])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def get_rank(cut):\n",
    "            # 返回在cut处切割后的大小与下标排列列表\n",
    "            return sorted(range(n), key = lambda i:nums[i][-cut:])\n",
    "        \n",
    "        return [get_rank(trim)[k-1] for k, trim in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def get_rank(cut):\n",
    "            # 返回在cut处切割后的大小与下标排列列表\n",
    "            return sorted(range(n), key = lambda i:nums[i][-cut:])\n",
    "        \n",
    "        return [get_rank(trim)[k-1] for k, trim in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def get_rank(cut):\n",
    "            # 返回在cut处切割后的大小与下标排列列表\n",
    "            return sorted(range(n), key = lambda i:nums[i][-cut:])\n",
    "        \n",
    "        return [get_rank(trim)[k-1] for k, trim in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(queries)\n",
    "        m=len(nums)\n",
    "        e=[]\n",
    "        for i in range(len(nums)):\n",
    "            e.append(list(str(nums[i])))\n",
    "        ans=[]\n",
    "        for i in range(n):  \n",
    "            rr=[]    \n",
    "            x=queries[i]\n",
    "            rr=[\"\".join((c[-x[1]:])) for c in e]\n",
    "            # print(rr)\n",
    "            cr=[(rr[i],i) for i in range(m)]\n",
    "            # print(cr)\n",
    "            cr.sort(key=lambda x:(x[0],x[1]))\n",
    "            # print(cr)\n",
    "            ans.append(cr[x[0]-1][1])\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(nums[0])\n",
    "        tm = [[] for _ in range(m + 1)]\n",
    "        for j, x in enumerate(nums):\n",
    "            for i in range(1, m + 1):\n",
    "                tm[i].append((int(x[-i:]), j))\n",
    "        for x in tm:\n",
    "            x.sort()\n",
    "        ans = []\n",
    "        for k, trim in queries:\n",
    "            ans.append(tm[trim][k-1][1])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
